package Algorithm_study.recursion_algorithm;

import java.util.Scanner;

/**
 * 用递归分支实现全排列问题！
 * @author YiWen Wan
 */
public class Permutation {
    public static void main(String[] args) {
        System.out.println("输入你想进行全排列的数据个数：");
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        int []data = new int[n];//用于接收进行全排列数据
        System.out.println("输入" + n + "个进行全排列的数据：");
        for (int i = 0;i< data.length;i++)
            data[i] = scanner.nextInt();
        System.out.println("输入数据完毕！");
        System.out.println("数据进行全排列的结果为：");
        Perm(data, 0);
        scanner.close();
    }

    /**
     * 用于进行全排列求解
     * @param data：等待全排列的数据
     * @param k：表示当前的排列数据进度
     */
    public static void Perm(int[] data,int k){
        if (k== data.length-1){//表示排列完了，可以输出一趟的结果了！
            for (int s:data
                 ) {
                System.out.print(s+" ");
            }
            System.out.println();
        }else{
            for (int i = k;i< data.length;i++){
                if (i>k){//向前面已经经历过的数据看看，有没有重复的，避免无用功！
                    for (int t = k; t<i ;t++){
                        if (data[i] == data[t])
                            return;
                    }
                }
                data[i] = (data[i]+data[k]) - (data[k]=data[i]);//交换数据
                Perm(data, k+1);//进行下一轮
                data[i] = (data[i]+data[k]) - (data[k]=data[i]);//换回来以保证逻辑的完整性
            }
        }
    }
}
